package com.lfg.leetcode.leetcode300;

import java.util.ArrayList;
import java.util.List;


public class No301removeInvalidParentheses {
    public static void main(String[] args) {
        List<String> ret = removeInvalidParentheses("(()(");
        for (String str : ret) {
            System.out.println("[" + str + "]");
        }
    }

    public static List<String> removeInvalidParentheses(String s) {
        if (null == s) {
            return new ArrayList<>(0);
        }
        int length = s.length();
        List<String> ret = new ArrayList<>(length);
        removeLeft(s, length - 1, length - 1, ret);
        if (ret.size() == 0) {
            ret.add("");
        }
        return ret;
    }

    public static void removeRight(String s, int last_i, int last_j, List<String> ret) {
        int cnt = 0;
        int length = s.length();
        for (int i = last_i; i >= 0 && i < length; i++) {
            char c = s.charAt(i);
            if (c == '(') {
                cnt++;
                continue;
            } else if (c == ')') {
                cnt--;
            }

            if (cnt >= 0) {
                continue;
            }

            for (int j = last_j; j >= 0 && j < length && j <= i; j++) {
                char c2 = s.charAt(j);
                if (c2 == ')' && (j == 0 || s.charAt(j - 1) != ')')) {
                    removeRight(s.substring(0, j) + s.substring(j + 1, length), i, j, ret);
                }
            }
            break;
        }
        if (cnt == 0) {
            ret.add(s);
        }

    }


    public static void removeLeft(String s, int last_i, int last_j, List<String> ret) {
        int length = s.length();
        int cnt = 0;
        for (int i = last_i; i >= 0; i--) {
            char c = s.charAt(i);
            if (c == ')') {
                cnt++;
                continue;
            } else if (c == '(') {
                cnt--;
            }
            if (cnt >= 0) {
                continue;
            }

            for (int j = last_j; j < length && j >= i; j--) {
                char c2 = s.charAt(j);
                if (c2 == '(' && (j == length - 1 || s.charAt(j + 1) != '(')) {
                    removeLeft(s.substring(0, j) + s.substring(j + 1, length), i - 1, j - 1, ret);
                }
            }
            return;
        }
        if (cnt > 0) {
            removeRight(s, 0, 0, ret);
        } else if (cnt == 0) {
            ret.add(s);
        }
    }
}
